import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class Solution90 {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        HashSet<List<Integer>> res = new HashSet<>();
        dfs(nums, 0, res, new ArrayList<>());
        return new ArrayList<>(res);
    }

    void dfs(int[] nums, int k, HashSet<List<Integer>> res, List<Integer> list) {
        if (k == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        dfs(nums, k + 1, res, list);
        list.add(nums[k]);
        dfs(nums, k + 1, res, list);
        list.remove(list.size() - 1);
    }
}
